import java.util.LinkedList;
import java.util.Random;
import java.io.*;

/**
 * An object representing set of elements in a random order.
 * Every time getNext() is called the next element is removed from the bag and returned.
 * 
 * @author (Oscar Ohlsson) 
 */
public class ShuffleBag <T> implements Serializable
{
    /** Used to generate random numbers internally */ 
    private Random rand;
    /** An array holding the elements */
    private LinkedList<T> sb;

    /**
     * Constructor for ShuffleBag
     * 
     * @param n     the number of elements in the bag
     * @param seed  a seed for the random generator 
     */
    public ShuffleBag(int seed)
    {
        rand = new Random(seed);
        sb = new LinkedList<T>();
    }
    
    /**
     * Shuffle the elements of the bag
     * 
     */
    public void shuffle() {
        if (!isEmpty()) {
            for (int i = 0; i < sb.size(); i++) {
                int j = rand.nextInt(sb.size());
                T x = sb.set(j,sb.getFirst());
                sb.set(0,x);
            }
        }
    }    
    
    /**
     * Add an element to the bag
     * 
     * @param x  the element to be added
     */
    public void add(T x) {
        sb.addFirst(x);
    }
    
    /**
     * Check if the bag is empty
     * 
     * @return  true if the bag is empty, false otherwise
     */
    public boolean isEmpty() {
        return sb.size() == 0;
    }
    
    /**
     * Get the number of elements in the bag
     * 
     * @return  the number of elements in the bag
     */
    public int size() {
        return sb.size();
    }
    
    /**
     * Get the next element from the bag. That element is removed from the bag.
     * 
     * @return  the next element from the bag
     */
    public T getNext() {
        return sb.removeFirst();
    }
    
    /**
     * Get the i:th element from the bag. That element is removed from the bag.
     * 
     * @param i   the index of the element
     * @return    the i:th element
     */
    public T get(int i) {
        return sb.get(i);
    }
}
